/**
 * https://leetcode.cn/submissions/detail/564519236/
 * 1011. 在 D 天内送达包裹的能力
 * Medium, 黄伟杰 2024.9.13
 * 二分查找
 */

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    int check(vector<int> &weights, int ans)
    {
        int days = 0;
        int res = 0;
        for (int i : weights)
        {
            res += i;
            if (res > ans)
            {
                res = i;
                days++;
            }
            if (res == ans)
            {
                res = 0;
                days++;
            }
        }
        if (res != 0)
            days++;
        return days;
    }

public:
    int shipWithinDays(vector<int> &weights, int days)
    {
        vector<int> a = weights;
        sort(a.begin(), a.end());
        int left = a.back(), right = 10e8 + 5; // 18
        while (left < right)
        {
            int mid = (right + left) / 2;
            if (check(weights, mid) > days)
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }
};